package yuan.algorithm.searching;

public class InterpolationSearch {

	public static int search(int[] inputs, int key){
		int begin = 0;
		int end = inputs.length-1;
		int	mid = 0;

		
		while(begin<=end ){
			if (begin == end)
				return inputs[0] == key?0:-1;
			
			mid = begin+ (key-inputs[begin])/(inputs[end]-inputs[begin])*(end-begin);
			
			if (mid<0||mid>=inputs.length)
				return -1;
			
			if (inputs[mid] == key)
				return mid;
			else if (inputs[mid]>key)
				end = mid-1;
			else
				begin = mid+1;
		}
		
		return -1;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		

	}

}
